﻿#include <iostream>
using namespace std;

const int n = 4;

int x[n] = {};													//皇后摆放在k行x[k]列

int place(int k) {												//考察皇后k放置在x[k]列是否发生冲突
	for(int i = 0; i < k; i++) {
		if(x[i] == x[k] || abs(i - k) == abs(x[i] - x[k])) {	//违反约束条件
			return 1;
		}
	}
	return 0;													//不冲突，返回0
}

void queen(int n) {												//求解n皇后问题
	int k = 0;
	while(k >= 0) {												//摆放皇后k，注意0≤k<n
		x[k]++;													//在下一列摆放皇后k
		while(x[k] < n && place(k) == 1) {						//发生冲突
			x[k]++;												//皇后k试探下一列
		}
		if(x[k] < n && k == n - 1) {							//得到一个解，输出
			for(int i = 0; i < n; i++) {
				cout << "x[" << i + 1 << "]:" << x[i] + 1<< " ";//数组下标从0开始，打印的列号从1开始
			}
			cout << endl;
			return;												//只求出一个解即可
		}
		if(x[k] < n && k < n - 1) {								//尚有皇后未摆放
			k = k + 1;											//准备摆放下一个皇后
		} else {
			x[k--] = -1;										//重置x[k]，回溯，重新摆放皇后k
		}
	}
	cout << "无解" << endl;
}

int main() {
	queen(n);

	system("pause");
	return 0;
}